Convex polygon¶
Time: O(N); Space: O(1); medium
Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).
Constraints:
There are at least 3 and at most 10,000 points.
Coordinates are in the range -10,000 to 10,000.
You may assume the polygon formed by given points is always a simple polygon (Simple polygon definition).
In other words, we ensure that exactly two edges intersect at each vertex, and that edges otherwise don’t intersect each other.
Example 1:
Input: points = [[0,0],[0,1],[1,1],[1,0]]
Output: True
Explanation:
Example 2:
Input: points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
Output: False
Explanation:
[3]:
class Solution1(object):
def isConvex(self, points):
"""
:type points: List[List[int]]
:rtype: bool
"""
def det(A):
return A[0][0]*A[1][1] - A[0][1]*A[1][0]
n, prev, curr = len(points), 0, None
for i in range(len(points)):
A = [[points[(i+j) % n][0] - points[i][0], points[(i+j) % n][1] - points[i][1]] for j in (1, 2)]
curr = det(A)
if curr:
if curr * prev < 0:
return False
prev = curr
return True
[4]:
s = Solution1()
points = [[0,0],[0,1],[1,1],[1,0]]
assert s.isConvex(points) == True
points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
assert s.isConvex(points) == False
2. Gift-Wrapping Algorithm¶
You can make things a lot easier than the Gift-Wrapping Algorithm…
that’s a good answer when you have a set of points w/o any particular boundary and need to find the convex hull.
A polygon is a set of points in a list where the consecutive points form the boundary.
It is much easier to figure out whether a polygon is convex or not (and you don’t have to calculate any angles, either):
For each consecutive pair of edges of the polygon (each triplet of points), compute the z-component of the cross product of the vectors defined by the edges pointing towards the points in increasing order.
Take the cross product of these vectors: * The polygon is convex if the z-components of the cross products are either all positive or all negative. * Otherwise the polygon is nonconvex.
Given p[k], p[k+1], p[k+2] each with coordinates x, y:
dx1 = x[k+1]-x[k]
dy1 = y[k+1]-y[k]
dx2 = x[k+2]-x[k+1]
dy2 = y[k+2]-y[k+1]
zcrossproduct = dx1 * dy2 - dy1 * dx2
If there are N points, make sure you calculate N cross products,
e.g. be sure to use the triplets (p[N-2],p[N-1],p[0]) and (p[N-1],p[0],p[1]).
[5]:
class Solution2(object):
def isConvex(self, points):
"""
:type points: List[List[int]]
:rtype: bool
"""
n = len(points)
zcrossproduct = None
for i in range(-2, n-2):
x = [ points[i][0], points[i+1][0], points[i+2][0] ]
y = [ points[i][1], points[i+1][1], points[i+2][1] ]
dx1 = x[1] - x[0]
dy1 = y[1] - y[0]
dx2 = x[2] - x[1]
dy2 = y[2] - y[1]
if not zcrossproduct:
zcrossproduct = dx1 * dy2 - dy1 * dx2
elif ( dx1 * dy2 - dy1 * dx2 ) * zcrossproduct < 0:
return False
return True
[6]:
s = Solution2()
points = [[0,0],[0,1],[1,1],[1,0]]
assert s.isConvex(points) == True
points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
assert s.isConvex(points) == False
[7]:
class Solution3(object):
def isConvex(self, points):
"""
:type points: List[List[int]]
:rtype: bool
"""
def crossProduct(p0, p1, p2):
x0, y0 = p0
x1, y1 = p1
x2, y2 = p2
return (x2 - x0) * (y1 - y0) - (x1 - x0) * (y2 - y0)
size = len(points)
last = 0
for x in range(size):
p0, p1, p2 = points[x], points[(x + 1) % size], points[(x + 2) % size]
p = crossProduct(p0, p1, p2)
if p * last < 0:
return False
last = p
return True
[8]:
s = Solution3()
points = [[0,0],[0,1],[1,1],[1,0]]
assert s.isConvex(points) == True
points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
assert s.isConvex(points) == False